#include <stdlib.h>
#include <string.h>
#include "fivekernel.h"
#include "ai.h"

static int scores[6][3]={
	{-1, HALF_1, LIVE_1},
	{-1, HALF_2, LIVE_2},
	{-1, HALF_3, LIVE_3},
	{-1, HALF_4, LIVE_4},
	{FIVE, FIVE, FIVE},
	{TOOLONG, TOOLONG, TOOLONG}
};

/*
 * computer函数，提供计算机对手。
 * 落子且转换turn后调用。
 * 参数：
 *  level: 智能级别。在程序里体现为嵌套深度。0～5，越来越高级。
 * 	board: 棋盘。正方形。
 * 	width: 棋盘大小width×width
 * 	xresult, yresult: 计算后认为可落子的坐标。
 *
 * 返回值：
 *  0： 表示运行正常。
 *  非0:有错误。
 *
 * TODO: 禁手
 */
int computer(int turn, int level, int **board, int width, int *xresult, int *yresult)
{
	int i, j;
	int x, y, w = width, num = 0;
	int oppo;
	int score 		= 0, scoremax 		= -FIVE*4;
	int	opposcore 	= 0, opposcoremax 	= -FIVE*4;
	int scoremaxtmp	= -FIVE*4;
	int stack[10][2], pos = 0;

	oppo = turn == BLACK?WHITE:BLACK;

	*xresult = *yresult = width/2;

	for(j = 0; j < w; j++){
		for(i = 0; i < w; i++){
			if(board[j][i] != EMPTY){
				++num;
				continue;
			}
			score		= point_score(turn, board, w, i, j, NULL);
			opposcore	= point_score(oppo, board, w, i, j, NULL);
			//我方有必胜的坐标
			if(score >= LIVE_3*2 && score > scoremax){
				scoremax = score;
				x = i;
				y = j;
			}

			//对方有必胜的坐标
			if(opposcore >= LIVE_3*2){
				if(opposcore > opposcoremax){
					opposcoremax = opposcore;
					*xresult = i;
					*yresult = j;
					pos = 0;
				}
				//对方必胜坐标不止一处，挑有利已方的一处
				else if(opposcore == opposcoremax &&\
						score > scoremaxtmp){
					scoremaxtmp = score;
					stack[pos][0] = i;
					stack[pos][1] = j;
					++pos;
				}
			}
		}
	}
	//已方落子，优势倍增
	if(scoremax*2 > opposcoremax){
		*xresult = x;
		*yresult = y;
	}
	if(scoremaxtmp > scoremax){
		pos = rand()%pos;
		*xresult = stack[pos][0];
		*yresult = stack[pos][1];
	}
	if(scoremax > 0 || opposcoremax > 0)
		return 0;
	
	//执白方由于先天劣势，防守四回合。
	if(turn == WHITE && num < 8)turn = oppo;
	pos = 0;
	for(i = 0; i < w; i++)
		for(j = 0; j < w; j++){
			if(board[j][i] != EMPTY)continue;

			{
				int xmin, ymin, xmax, ymax;

				xmin = i - 2 >= 0 ? i - 2 :0 ;
				ymin = j - 2 >= 0 ? j - 2 :0 ;
				xmax = i + 2 <= w ? i + 2 :w ;
				ymax = j + 2 <= w ? j + 2 :w ;

				int ii, jj;
				int flag=0;
				for(ii=xmin; ii<xmax; ii++)
					for(jj=ymin; jj<ymax; jj++){
						if(board[jj][ii] != EMPTY)flag=1;
					}

				if(flag == 0)
					continue;
			}
			score = ai(level*2, turn, board, w, i, j);
			if(score > scoremax){
				pos = 0;
				scoremax = score;
				*xresult = i;
				*yresult = j;
			}
			else if(score == scoremax && pos<10){
				stack[pos][0]=i;
				stack[pos][1]=j;
				++pos;
			}
		}
	if(pos){
		pos = rand()%pos;
		*xresult = stack[pos][0];
		*yresult = stack[pos][1];
	}
	return 0;
}

inline int point_score(int turn, int **board, int w, int x, int y, int *result)
{
	int i, j;
	int sum;
	int live;
	int score[4];

	//横向判断
	{
		sum = 1;
		live = 0;
		j   = y;
		//左：
		i = x - 1;
		while(i >= 0 && board[j][i] == turn){
			++sum;
			--i;
		}
		if(i >=0 && board[j][i] == EMPTY)
			++live;
		//右：
		i = x + 1;
		while(i < w && board[j][i] == turn){
			++sum;
			++i;
		}
		if(i < w && board[j][i] == EMPTY)
			++live;
		if(sum > 5)sum=6;
		score[0] = scores[sum - 1][live];
	}

	//纵向判断
	{
		sum = 1;
		live = 0;
		i   = x;
		//上：
		j = y - 1;
		while(j >= 0 && board[j][i] == turn){
			++sum;
			--j;
		}
		if(j >= 0 && board[j][i] == EMPTY)
			++live;

		//下：
		j = y + 1;
		while(j < w && board[j][i] == turn){
			++sum;
			++j;
		}
		if(j < w && board[j][i] == EMPTY)
			++live;
		if(sum > 5)sum=6;
		score[1] = scores[sum - 1][live];
	}

	//正斜向判断
	{
		sum = 1;
		live = 0;
		//左上：
		i = x - 1;
		j = y - 1;
		while(j >= 0 && i >=0 && board[j][i] == turn){
			++sum;
			--j, --i;
		}
		if(j >= 0 && i >=0 && board[j][i] == EMPTY)
			++live;
		//右下：
		i = x + 1;
		j = y + 1;
		while(j < w && i < w && board[j][i] == turn){
			++sum;
			++j, ++i;
		}
		if(j < w && i < w && board[j][i] == EMPTY)
			++live;
		if(sum > 5)sum=6;
		score[2] = scores[sum - 1][live];
	}

	//反斜向判断
	{
		sum = 1;
		live = 0;
		//右上：
		i = x + 1;
		j = y - 1;
		while(j >= 0 && i < w && board[j][i] == turn){
			++sum;
			--j, ++i;
		}
		if(j >= 0 && i < w && board[j][i] == EMPTY)
			++live;
		//左下：
		i = x - 1;
		j = y + 1;
		while(j < w && i >=0 && board[j][i] == turn){
			++sum;
			++j, --i;
		}
		if(j < w && i >=0 && board[j][i] == EMPTY)
			++live;
		if(sum > 5)sum=6;
		score[3] = scores[sum - 1][live];
	}
	sum = 0;
	sum += score[0]>0?score[0]:0;
	sum += score[1]>0?score[1]:0;
	sum += score[2]>0?score[2]:0;
	sum += score[3]>0?score[3]:0;
	if(result)
		memcpy(result, score, sizeof(int)*4);
	
	int live3 = 0;
	int liveorhalf4 = 0;
	int toolong = 0;
	for(i=0; i<4; i++){
		switch(score[i]){
			case TOOLONG:
				++toolong;
				break;
			case FIVE:
				return FIVE;
			case LIVE_3:
				++live3;
				break;
			case HALF_4:
			case LIVE_4:
				++liveorhalf4;
				break;
		}
	}
	if(turn == BLACK){
		if(toolong > 0)
			sum = -FIVE*4;
		if(liveorhalf4 >= 2)
			sum = -FIVE*4;
		else if(live3 >=2)
			sum = -FIVE*4;
	}
	if(liveorhalf4==1 && live3==1)
		sum += LIVE_3_4;
	return sum;
}

int ai(int level, int turn, int **board, int width, int x, int y)
{
	int i, j;
	int score = 0, scoremax = -FIVE*4;
	int xmin, ymin, xmax, ymax;
	int w = width;
	int oppo = turn == BLACK?WHITE:BLACK;

	score = point_score(turn, board, w, x, y, NULL);
	if(score > scoremax)
		scoremax = score;

	if(level){
		xmin = x - 2 >= 0 ? x - 2 :0 ;
		ymin = y - 2 >= 0 ? y - 2 :0 ;
		xmax = x + 2 <= w ? x + 2 :w ;
		ymax = y + 2 <= w ? y + 2 :w ;
		for(i=xmin; i<xmax; i++){
			for(j=ymin; j<ymax; j++){
				if(board[j][i]!=EMPTY)continue;
				board[j][i] = turn;
				int sc = ai(level-1, oppo, board, width, x, y);
				if(score - sc > scoremax)
					scoremax = score - sc;
				board[j][i] = EMPTY;
			}
		}
	}
	return scoremax;
}

inline int is_forbidden(int *score)
{
	int i;
	int live3 = 0;
	int liveorhalf4 = 0;
	int toolong = 0;
	for(i=0; i<4; i++){
		switch(score[i]){
			case TOOLONG:
				++toolong;
			case FIVE:
				return 0;
			case LIVE_3:
				++live3;
				break;
			case HALF_4:
			case LIVE_4:
				++liveorhalf4;
				break;
		}
	}
	if(toolong > 0)
		return -6;
	if(liveorhalf4 >= 2)
		return -4;
	else if(live3 >=2)
		return -3;
	return 0;
}
